3737. Куча ли?

Структуру данных Куча можно реализовать на основе массива.

Для этого должно выполняться основное свойство кучи, которое заключается в следующем. Для каждого i (1 ≤ i ≤ n) выполняются следующие условия:

· Если 2i ≤ n, то a[i] ≤ a[2i]

· Если 2i + 1 ≤ n, то a[i] ≤ a[2i + 1]

Дан массив целых чисел. Определите, является ли он кучей.

Вход. Первая строка содержит целое число n (1 ≤ n ≤ 10⁵). Вторая строка содержит n целых чисел по модулю не превосходящих 2 * 10⁹.

Выход. Выведите “YES”, если массив является кучей и “NO” в противном случае.

Пример входа	Пример выхода
7 3 10 5 12 11 6 7	YES

РЕШЕНИЕ

куча

Анализ алгоритма

Для каждого индекса i входного массива следует проверить выполнимость условия кучи. Значение i достаточно перебрать от 1 до n / 2.

Пример

Куча, приведенная в примере, имеет вид:

Реализация алгоритма

Для хранения входных чисел объявим массив m.

#define MAX 100010

int m[MAX];

Читаем входные данные.

scanf("%d",&n);

for(i = 1; i <= n; i++)

scanf("%d",&m[i]);

Двигаемся по массиву с начала и до середины. Проверяем условие выполнения кучи. Если на какой-то итерации условие не выполняется, то устанавливаем flag = 1 и выходим из цикла.

flag = 0;

for (i = 1; i <= n / 2; i++)

{

if ((2 * i <= n) && (m[i] > m[2 * i]))

{

flag = 1; break;

}

if ((2 * i + 1 <= n) && (m[i] > m[2 * i + 1]))

{

flag = 1; break;

}

}

В зависимости от значения переменой flag выводим ответ.

if (flag == 1) printf("NO\n"); else printf("YES\n");

Java реализация

import java.util.*;

public class Main {

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n+1];

for(int i = 1; i <= n; i++)

m[i] = con.nextInt();

int flag = 0;

for (int i = 1; i <= n / 2; i++)

{

if ((2 * i <= n) && (m[i] > m[2 * i]))

{

flag = 1; break;

}

if ((2 * i + 1 <= n) && (m[i] > m[2 * i + 1]))

{

flag = 1; break;

}

}

if (flag == 1) System.out.println("NO");

else System.out.println("YES");

con.close();

}

}